package code.BinaryTree;

import code.Strings.KMP;
import struct.Record;
import struct.Tree;
import struct.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

// 查找子树的相关代码
public class SubTree {
	public static void main(String[] args) {
		SubTree subTree = new SubTree();
		TreeNode tree = Tree.constructTree("[6,1,12,0,3,10,13,null,null,null,null,4,14,20,16,2,5,11,15]");
		TreeNode treeNode = subTree.biggestSubBST(tree);
		System.out.println(treeNode);

//		tree = Tree.constructTree("[1,2,3,4,null,2,4,null,null,4]");
//		List<TreeNode> duplicateSubtrees = subTree.findDuplicateSubtrees(tree);
//		System.out.println(duplicateSubtrees);

		System.out.print("找到二叉树中符合搜索二叉树条件的最大拓扑结构:");
		int bstTopoSize = subTree.bstTopoSize(tree);
		System.out.println("\n\t\t" + bstTopoSize);
		int bstTopoSize2 = subTree.bstTopoSize2(tree);
		System.out.println("\t\t" + bstTopoSize2);

		System.out.print("判断t1树中是否有与t2树拓扑结构完全相同的子树:");
		TreeNode t1 = Tree.constructTree("[1,2,3,4,5,6,7,null,8,9]");
		TreeNode t2 = Tree.constructTree("[2,4,5,null,8]");
		boolean contains = subTree.contains(t1, t2);
		System.out.println(contains);

		System.out.print("判断t1树中是否包含t2树全部的拓扑结构|572 另一个树的子树:");
		TreeNode tree1 = Tree.constructTree("[12]");
		TreeNode tree2 = Tree.constructTree("[2]");
		boolean subTree1 = subTree.isSubTree(tree1, tree2);
		System.out.print(subTree1);
		boolean b = subTree.isSubTree2(tree1, tree2);
		System.out.println("\t\t" + b);
		System.out.println();


		System.out.print("面试题 04.05. 合法二叉搜索树:");
		TreeNode tree3 = Tree.constructTree("[1,1]");
		boolean validBSTH2 = subTree.isValidBST(tree3);
		System.out.println(validBSTH2);
		boolean validBST2 = subTree.isValidBST2(tree3);
		System.out.println(validBST2);

		System.out.print("1110. 删点成林");
		TreeNode tree4 = Tree.constructTree("[1,2,3,4,5,6,7]");
		List<TreeNode> treeNodes = subTree.delNodes(tree4, new int[]{3, 5});
		System.out.println(treeNodes);

	}

	//找到二叉树中最大的搜索二叉子树
	public TreeNode biggestSubBST(TreeNode head) {
		int[] ints = new int[3];
		return biggestSubBSTHelper(head, ints);
	}

	public TreeNode biggestSubBSTHelper(TreeNode head, int[] ints) {
		if (head == null) {
			ints[0] = 0;
			ints[1] = Integer.MAX_VALUE;
			ints[2] = Integer.MIN_VALUE;
			return null;
		}
		TreeNode lBST = biggestSubBSTHelper(head.left, ints);
		int lSize = ints[0];
		int lMin = ints[1];
		int lMax = ints[2];
		TreeNode rBST = biggestSubBSTHelper(head.right, ints);
		int rSize = ints[0];
		int rMin = ints[1];
		int rMax = ints[2];
		ints[1] = Math.min(lMin, head.val);
		ints[2] = Math.max(rMax, head.val);
		if (head.left == lBST && head.right == rBST && head.val > lMax && head.val < rMin) {
			ints[0] = rSize + lSize + 1;
			return head;
		}
		ints[0] = Math.max(lSize, rSize);
		return lSize > rSize ? lBST : rBST;
	}

	//652. 寻找重复的子树
	public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
		List<TreeNode> treeNodes = new ArrayList<>();
		HashMap<String, Integer> hashMap = new HashMap<>();
		findDuplicateSubtreesHelper(root, hashMap, treeNodes);
		return treeNodes;
	}

	public String findDuplicateSubtreesHelper(TreeNode root, HashMap<String, Integer> hashMap, List<TreeNode> treeNodes) {
		if (root == null) {
			return "#";
		}

		String lStr = findDuplicateSubtreesHelper(root.left, hashMap, treeNodes);
		String rStr = findDuplicateSubtreesHelper(root.right, hashMap, treeNodes);
		String nStr = root.val + "," + lStr + "," + rStr;
		hashMap.put(nStr, hashMap.getOrDefault(nStr, 0) + 1);
		if (hashMap.get(nStr) == 2) {
			treeNodes.add(root);
		}
		return nStr;
	}

	//找到二叉树中符合搜索二叉树条件的最大拓扑结构
	public int bstTopoSize(TreeNode head) {
		if (head == null) {
			return 0;
		}
		int max = maxTopo(head, head);
		max = Math.max(bstTopoSize(head.left), max);
		max = Math.max(bstTopoSize(head.right), max);
		return max;
	}

	public int maxTopo(TreeNode head, TreeNode cur) {
		if (head != null && cur != null && isBSTNode(head, cur)) {
			return maxTopo(head, cur.left) + maxTopo(head, cur.right) + 1;
		}
		return 0;
	}

	public boolean isBSTNode(TreeNode head, TreeNode cur) {
		if (head == null) {
			return false;
		}
		if (head.val == cur.val) {
			return true;
		}
		return isBSTNode(head.val > cur.val ? head.left : head.right, cur);
	}

	//找到二叉树中符合搜索二叉树条件的最大拓扑结构-解法2
	public int bstTopoSize2(TreeNode head) {
		HashMap<TreeNode, Record> hashMap = new HashMap<>();
		return bstTopoSize2Helper(head, hashMap);
	}

	public int bstTopoSize2Helper(TreeNode head, HashMap<TreeNode, Record> hashMap) {
		if (head == null) {
			return 0;
		}
		int ls = bstTopoSize2Helper(head.left, hashMap);
		int rs = bstTopoSize2Helper(head.right, hashMap);
		modifyMap(head.left, head.val, hashMap, true);
		modifyMap(head.right, head.val, hashMap, false);
		Record lRecord = hashMap.get(head.left);
		Record rRecord = hashMap.get(head.right);
		int lBST = lRecord == null ? 0 : lRecord.l + lRecord.r + 1;
		int rBST = rRecord == null ? 0 : rRecord.l + rRecord.r + 1;
		hashMap.put(head, new Record(lBST, rBST));
		return Math.max(lBST + rBST + 1, Math.max(ls, rs));
	}

	public int modifyMap(TreeNode head, int value, HashMap<TreeNode, Record> hashMap, boolean s) {
		if (head == null || !hashMap.containsKey(head)) {
			return 0;
		}
		Record record = hashMap.get(head);
		if ((s && head.val > value) || ((!s) && head.val < value)) {
			hashMap.remove(head);
			return record.l + record.r + 1;
		}
		int minus = modifyMap(s ? head.right : head.left, value, hashMap, s);
		if (s) {
			record.r = record.r - minus;
		} else {
			record.l = record.l - minus;
		}
		hashMap.put(head, record);
		return minus;
	}

	//判断t1树中是否包含t2树全部的拓扑结构
	public boolean contains(TreeNode t1, TreeNode t2) {
		if (t1 == null) {
			return false;
		}
		return check(t1, t2) || contains(t1.left, t2) || contains(t1.right, t2);
	}

	public boolean check(TreeNode t1, TreeNode t2) {
		if (t2 == null) {
			return true;
		}
		if (t1 == null || t1.val != t2.val) {
			return false;
		}
		return check(t1.left, t2.left) && check(t1.right, t2.right);
	}


	//判断t1树中是否包含t2树全部的拓扑结构
	//572. 另一个树的子树
	public boolean isSubTree(TreeNode t1, TreeNode t2) {
		if (t1 == null) {
			return false;
		}
		return isSbuTreeH(t1, t2) || isSubTree(t1.left, t2) || isSubTree(t1.right, t2);
	}

	public boolean isSbuTreeH(TreeNode t1, TreeNode t2) {
		if (t1 == null && t2 == null) {
			return true;
		}
		if (t1 == null || t2 == null || t1.val != t2.val) {
			return false;
		}
		return isSbuTreeH(t1.left, t2.left) && isSbuTreeH(t1.right, t2.right);
	}

	//判断t1树中是否包含t2树全部的拓扑结构
	//572. 另一个树的子树
	public boolean isSubTree2(TreeNode t1, TreeNode t2) {
		//序列化
		Serialization serialization = new Serialization();
		String serialize = "!" + serialization.serialize(t1);
		String serialize1 = "!" + serialization.serialize(t2);
		serialize.contains(serialize1);
		KMP kmp = new KMP(serialize1);
		int search = kmp.search(serialize);
		return search != -1;
	}

	//700. 二叉搜索树中的搜索
	public TreeNode searchBST(TreeNode root, int val) {
		TreeNode result = null;
		searchBSTH(root, result, val);
		return result;
	}

	public void searchBSTH(TreeNode root, TreeNode result, int val) {
		if (root == null) {
			return;
		}
		if (val == root.val) {
			result = root;
			return;
		}
		searchBSTH(root.left, result, val);
		searchBSTH(root.right, result, val);
	}


	//100.相同的树
	public boolean isSameTree(TreeNode p, TreeNode q) {
		if (p == null && q == null) {
			return true;
		}
		if (p == null || q == null || q.val != p.val) {
			return false;
		}
		return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
	}

	//101.对称二叉树
	public boolean isSymmetric(TreeNode root) {
		if (root == null) {
			return true;
		}
		return isSameTree(root.left, root.right);
	}

	//面试题 04.05. 合法二叉搜索树
	public boolean isValidBST(TreeNode root) {
		return isValidBSTHelper(root, root);
	}

	public boolean isValidBSTHelper(TreeNode root, TreeNode node) {
		if (node == null) {
			return true;
		}
		return isValidBSTSearch(root, node) && isValidBSTHelper(root, node.left) && isValidBSTHelper(root, node.right);
	}

	public boolean isValidBSTSearch(TreeNode root, TreeNode node) {
		if (root == null) {
			return false;
		} else if (root == node) {
			return true;
		} else if (root.val == node.val) {
			return false;
		}
		return root.val > node.val ? isValidBSTSearch(root.left, node) : isValidBSTSearch(root.right, node);
	}

	public boolean isValidBST2(TreeNode root) {
		Integer[] initNum = new Integer[1];
		return isValidBST2Helper(root, initNum);
	}

	public boolean isValidBST2Helper(TreeNode root, Integer[] initNum) {
		if (root == null) {
			return true;
		}
		boolean validBST2Helper = isValidBST2Helper(root.left, initNum);
		if (!validBST2Helper) {
			return false;
		}
		if (initNum[0] != null && initNum[0] >= root.val) {
			return false;
		}
		initNum[0] = root.val;

		boolean validBST2Helper1 = isValidBST2Helper(root.right, initNum);
		if (!validBST2Helper1) {
			return false;
		}
		return true;
	}

	public List<TreeNode> delNodes(TreeNode root, int[] to_delete) {
		List<TreeNode> treeNodes = new ArrayList<>();
//		HashSet<Integer> hashSet = new HashSet<>();
		HashMap<Integer, Integer> hashSet = new HashMap<>();
		for (int i = 0; i < to_delete.length; i++) {
			hashSet.put(to_delete[i], 0);
		}
		TreeNode cur = new TreeNode(0);
		cur.right = root;
		delNodesH(root, cur, hashSet, treeNodes);
		if (cur.right != null) {
			treeNodes.add(cur.right);
		}
		return treeNodes;
	}

	public void delNodesH(TreeNode root, TreeNode cur, HashMap<Integer, Integer> hashSet, List<TreeNode> treeNodes) {
		if (root == null) {
			return;
		}

		delNodesH(root.left, root, hashSet, treeNodes);
		delNodesH(root.right, root, hashSet, treeNodes);

		//判断是不是在集合里
		if (hashSet.containsKey(root.val)) {
			if (root.left != null) {
				treeNodes.add(root.left);
			}
			if (root.right != null) {
				treeNodes.add(root.right);
			}
			if (cur.left == root) {
				cur.left = null;
			} else if (cur.right == root) {
				cur.right = null;
			}
		}

	}
}

